package lib

func init() {
	Probs = append(Probs, Problem{
		Num:         72,
		Discription: "编辑距离",
		Level:       3,
		Labels: map[string]int{
			"动态规划": 1,
		},
	})
}

// MinDistance 从word1到word2有三种操作：插入、替换、删除，操作的位置不重要，有论文证明是等效的
//  @param word1
//  @param word2
//  @return int
func MinDistance(word1 string, word2 string) int {
	m := len(word1)
	n := len(word2)
	if m == 0 {
		return n
	}

	if n == 0 {
		return m
	}

	//dp[i][j]表示从word1[:i]变到word2[:j]最少需要几步操作
	dp := make([][]int, m+1)
	for i := 0; i <= m; i++ {
		dp[i] = make([]int, n+1)
	}

	//初始化i或者j为0的情况
	dp[0][0] = 0
	for i := 1; i <= m; i++ {
		dp[i][0] = i
	}
	for j := 1; j <= n; j++ {
		dp[0][j] = j
	}

	//如果word1[i-1] == word2[j-1]，那么dp[i][j] = dp[i-1][j-1]
	for i := 1; i <= m; i++ {
		for j := 1; j <= n; j++ {
			if word1[i-1] == word2[j-1] {
				dp[i][j] = dp[i-1][j-1]
			} else {
				//不等于的话从删除、替换、插入里选操作数最小的+1
				//删除：word1[:i]删除最后一个字符变成word1[:i-1]，再加上dp[i-1][j]
				//替换：word1[:i-1]先变成word2[:j-1]，word1[i-1]再替换成word2[j-1]
				//插入：word1[:i]先变成word2[:j-1]，再在末尾插入word2[j-1]
				dp[i][j] = min(dp[i-1][j-1], dp[i][j-1], dp[i-1][j]) + 1
			}
		}
	}

	return dp[m][n]
}
